package sorter;

/**
 * 堆排序：首先，在[0,...,len-1]范围内建立大根堆，将arr[0]与arr[len-1]交换，再在[0,...,len-2]范围内建立大根堆，直到[0,1]。
 * 时间复杂度：O(nlog(n))
 * 稳定性：由于是跳跃比较，并非两两相邻比较，因此是非稳定的。
 * @author Zhang Ziyi
 */
public class HeapSorter implements Sorter{

    @Override
    public void sort(int[] arr) {
        heapSort(arr);
    }

    private void heapSort(int[] arr) {
        for (int i = arr.length; i > 0; i--) {
            // 建立[0,i)范围内的大根堆，则下标 0 处的结点值是最大的
            buildMaxHeap(arr, i);
            // 将最大值交换到最右侧
            swap(arr, 0, i - 1);
        }
    }

    /**
     * 在[0,endExclusive)范围建立大根堆
     * 从最后一个非叶子结点开始向左、向上遍历，看其是否为大根堆，若不是，把大的交换上来，交换下去的结点就不一定能当大根了，需要再比较交换，递归地进行下去。
     *
     */
    private void buildMaxHeap(int[] arr, int endExclusive) {
        // 最后一个非叶子结点
        int lastNotLeafNode = endExclusive / 2 - 1;
        for (int i = lastNotLeafNode; i >= 0; i--) {
            compareAndSwap(i, arr, endExclusive);
        }
    }

    /**
     * 比较并交换 index 及其左右孩子，若进行了交换，则递归地进行下去
     */
    private void compareAndSwap(int index, int[] arr, int endExclusive) {
        int largestIndex = findLargestIndex(index, arr, endExclusive); // 找到最大者下标
        if (index != largestIndex) { // 父结点值不是最大的，需要交换
            swap(arr, index, largestIndex);
            compareAndSwap(largestIndex, arr, endExclusive);
        }
    }

    /**
     * 寻找下标为 defaultIndex 的结点和其左右孩子中最大者的下标
     * @param defaultIndex 父结点下标
     * @param arr 数组
     * @param endExclusive 范围(不包括)
     */
    private int findLargestIndex(int defaultIndex, int[] arr, int endExclusive) {
        int largestIndex = defaultIndex;
        int leftChildIndex = 2 * defaultIndex + 1, rightChildIndex = 2 * defaultIndex + 2;
        if (leftChildIndex < endExclusive && arr[leftChildIndex] > arr[largestIndex]) {
            largestIndex = leftChildIndex;
        }
        if (rightChildIndex < endExclusive && arr[rightChildIndex] > arr[largestIndex]) {
            largestIndex = rightChildIndex;
        }
        return largestIndex;
    }
}
